package master;

import java.util.List;

/**
 * 反转链表2
 *
 * @author chenyw
 * @date 2022/7/28 19:00
 */
public class M92reverseBetween {
    //头插法，一次遍历； 穿针引线
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode curr = pre.next;
        ListNode next;
        //头插法,将cur的下一个节点查到pre的下一个位置
        for (int i = 0; i < right - left; i++) {
            next = curr.next;
            curr.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }



    //需要量趟遍历
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if (left == right || head == null || head.next == null) {
//            return head;
//        }
//        ListNode p = head;
//        int len = 0;
//        while (p != null) {
//            p = p.next;
//            len++;
//        }
//        //头结点没有前节点就创造一个前节点
//        ListNode pre = new ListNode(-1);
//        ListNode res = pre;
//        pre.next = head;
//        left = len - left + 1;
//        right = len - right;
////        ListNode pre = head;
//        ListNode t = head;
//        p = head;
//        int count = 0;
//        while (p != null) {
//            p = p.next;
//            if (count >= left) {
//                pre = pre.next;
//                System.out.println(pre.val);
//            }
//            if (count >= right) {
//                t = t.next;
//                System.out.println(t== null);
//            }
//            count++;
//        }
//        //q表示前一个节点
//        ListNode q = t;
//        ListNode cur = pre.next;
//        while (cur != t) {
//            p = cur.next;
//            cur.next = q;
//            q = cur;
//            cur = p;
//        }
//        pre.next = q;
//        return res.next;
//    }
}
